package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * 18. 四数之和
 * https://leetcode-cn.com/problems/4sum/description/
 */
public class FourSum {

    public List<List<Integer>> fourSum(int[] nums, int target){
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        int len = nums.length;
        for(int i = 0; i < len - 3; i++){
            for(int j = i + 1; j < len - 2; j++){
                for(int k = j + 1; k < len - 1; k++){
                    for(int l = k + 1; l < len; l++){
                        int sum = nums[i] + nums[j] + nums[k] + nums[l];
                        if(sum == target){
                            List<Integer> temp = new ArrayList<>();
                            temp.add(nums[i]);
                            temp.add(nums[j]);
                            temp.add(nums[k]);
                            temp.add(nums[l]);
                            boolean flag = true;
                            for(List<Integer> item: res){
                                if(item.get(0) < temp.get(0)){
                                    continue;
                                }else if(item.get(0) > temp.get(0)){
                                    break;
                                }
                                if(item.get(1) < temp.get(1)){
                                    continue;
                                }else if(item.get(1) > temp.get(1)){
                                    break;
                                }
                                if(item.get(2) < temp.get(2)){
                                    continue;
                                }else if(item.get(2) > temp.get(2)){
                                    break;
                                }
                                if(item.get(3) < item.get(3)){
                                    continue;
                                }else if(item.get(3) > temp.get(3)){
                                    break;
                                }else{
                                    flag = false;
                                    break;
                                }
                            }
                            if(flag){
                                res.add(temp);
                            }
                        }
                    }
                }
            }
        }
        return res;
    }

    private void find(int[] nums, int index1, int index4, int target, List<List<Integer>> res){
        if(index1 >= index4 - 2){
            return;
        }
        int index2 = index1 + 1, index3  = index4 - 1;
        while (index2 < index3){
            int sum = nums[index1] + nums[index2] + nums[index3] + nums[index4];
            if(sum == target){
                boolean addFlag = true;
                if(addFlag){
                    List<Integer> temp = new ArrayList<>();
                    temp.add(nums[index1]);
                    temp.add(nums[index2]);
                    temp.add(nums[index3]);
                    temp.add(nums[index4]);
                    res.add(temp);
                }
                index2++;
                index3--;
            }else if(sum > target){
                index3--;
                if(index3 <= index2){
                    break;
                }
            }else{
                index2++;
                if(index2 >= index3){
                    break;
                }
            }
        }
        find(nums, index1++, index4, target, res);
        find(nums, index1, index4--, target, res);
    }

    public static void main(String[] args) {
        int[] nums = {-3,-1,0,2,4,5};
        int target = 2;
        new FourSum().fourSum(nums, target);
    }

}
